package collections;

import java.util.Comparator;
import java.util.Random;
import java.util.RandomAccess;

import collections.list.MyList;
import collections.list.array_list.MyArrayList;
import collections.list.linked_list.MyLinkedList;

public class MyCollections {
	
	public static <T extends Comparable<? super T>>  void sort(MyList<T> list){
		if(list instanceof RandomAccess){
			sort(list, 0, list.size() - 1);
		} else {
			bubleSort(list);
		}
	}
	
	private static <T extends Comparable<? super T>>  void sort(MyList<T> list, int indexFrom, int indexTo){
		int size = (indexTo - indexFrom) + 1;
        int first = indexFrom;
        int last = indexTo;
        T x = list.get(indexFrom + size/2);
        while (first < last) {
            while (list.get(first).compareTo(x) < 0) {
                first++;
            }
            while (list.get(last).compareTo(x) > 0) {
                last--;
            }
            if (first < last) {
                MyCollections.swap(list,first,last);
                first++;
                last--;
            }
        }
        if(last > (indexFrom + 1)){
        	sort(list, indexFrom, last);
        	
        }
        if(first > indexTo){
        	sort(list, first, indexTo);
        }
	}
	
	private static <T extends Comparable<? super T>>  void bubleSort(MyList<T> list) {
		for (int count = list.size() - 1; count > 0; count--) {
			for (int i = 0; i < count; i++) {
				if (list.get(i).compareTo(list.get(i + 1)) > 0) {
					swap(list, i, i + 1);
				}
			}
		}
	}
	
	public static <T> void sort(MyList<T> list, Comparator<T> comparator){
		if(list instanceof RandomAccess){
			sort(list, 0, list.size() - 1, comparator);
		} else {
			bubleSort(list, comparator);
		}
	}
	
	private static <T>  void sort(MyList<T> list, int indexFrom, int indexTo, Comparator<T> comparator){
		int size = indexTo - indexFrom;
        int first = indexFrom;
        int last = indexTo;
        T x = list.get(list.size()/2);
        while (first <= last) {
            while (comparator.compare(list.get(first), x) < 0) {
                first++;
            }
            while (comparator.compare(list.get(last), x) > 0) {
                last--;
            }
            if (first <= last) {
                MyCollections.swap(list,first,last);
                first++;
                last--;
            }
        }
        if(last > (indexFrom + 1)){
        	sort(list, indexFrom, last, comparator);
        	
        }
        if(first > indexTo){
        	sort(list, first, indexTo, comparator);
        }
	}
	
	private static <T>  void bubleSort(MyList<T> list, Comparator<T> comparator) {
		for (int count = list.size() - 1; count > 0; count--) {
			for (int i = 0; i < count; i++) {
				T first = list.get(i);
				T second = list.get(i + 1);
				int r = comparator.compare(first, second);
				if (r > 0) {
					swap(list, i, i + 1);
				}
			}
		}
	}
	
	public static <T> void swap(MyList<T> list, int i, int j){
		T temp = list.get(i);
		list.set(i, list.get(j));
		list.set(j, temp);
	}
	
	public static <T> void copy(MyList<T> dest, MyList<T> src){
		dest.clear();
		for(T element: src){
			dest.add(element);
		}
	}
	
	public static <T> void reverse(MyList<T> list){
		int j = list.size() - 1;
		for(int i = 0; i <= (list.size()/2) - 1; i++) {
			swap(list, i, j);
			j--;
		}
	}
	
	public static <T extends Comparable<? super T>> int binarySearch(RandomAccess list, T key) {
		MyList<T> currentList = (MyList<T>)list;
		int first = 0;
		int last = currentList.size() - 1;		
		int	middle = currentList.size()/2;
		T temp;
		while(first <= last){			
			temp = currentList.get(middle);
			if(key.equals(temp)) {
				return middle;
			}else if(temp.compareTo(key) > 0){				
				last = middle - 1;
				
			} else if(temp.compareTo(key) < 0){
				first = middle + 1;
			}		
			middle = (int) Math.round((last + first)/2d);
		}
		return -(middle) - 1;
	}
}
